package com.fulin.leetcode;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 最长有效括号的长度
 *
 * @Author fulin
 * @Date 2022/9/15 09:57
 **/
public class Num32 {

    //使用栈的方式来解决
    public int longestValidParentheses(String s) {
        int len = s.length();
        int[] flag = new int[len];
        if(len <= 1) return 0;
        int maxVal = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for(int i = 0; i < len ; i++){
            char c = s.charAt(i);
            if(c == '('){
                stack.push(i);
            }else{
                stack.pop();
                if(stack.isEmpty()){
                    //栈底元素一定是到目前为止
                    stack.push(i);
                }else {
                    maxVal = Math.max(maxVal,i - stack.peek());
                }
            }
        }
        return maxVal;
    }

    /**
     * 使用动态规划的方式来解决
     * @param s
     * @return
     */
    public int longestValidParentheses2(String s) {
        int len = s.length();
        if(len <= 1) return 0;

        int[] pd = new int[len];
        return 0;
    }
}
